package search.binarySearch;

public class BinarySearch {

    private BinarySearch() {
    }

    // 非递归的二分查找法
    public static <E extends Comparable<E>> int search(E[] data, E target) {
        int l = 0, r = data.length - 1;
        // 在data[l,r]的范围内查找target
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) == 0) {
                return mid;
            }
            if (data[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }

    public static int search(int[] data, int target) {
        int l = 0, r = data.length - 1;
        // 在data[l,r]的范围内查找target
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (data[mid] == target) {
                return mid;
            }
            if (data[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }

    // 递归的二分查找法
    public static <E extends Comparable<E>> int searchR(E[] data, E target) {
        return searchR(data, 0, data.length - 1, target);
    }

    private static <E extends Comparable<E>> int searchR(E[] data, int l, int r, E target) {
        if (l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        if (data[mid].compareTo(target) == 0) {
            return mid;
        }
        if (data[mid].compareTo(target) < 0) {
            return searchR(data, mid + 1, r, target);
        }
        if (data[mid].compareTo(target) > 0) {
            return searchR(data, 0, mid - 1, target);
        }
        return -1;
    }

    public static int searchR(int[] data, int target) {
        return searchR(data, 0, data.length - 1, target);
    }

    private static int searchR(int[] data, int l, int r, int target) {
        if (l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        if (data[mid] == target) {
            return mid;
        }
        if (data[mid] < target) {
            return searchR(data, mid + 1, r, target);
        }
        if (data[mid] > target) {
            return searchR(data, 0, mid - 1, target);
        }
        return -1;
    }

    // > target 的最小值的索引
    private static <E extends Comparable<E>> int upper(E[] data, E target) {
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) <= 0) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    // > target ，返回最小值的索引
    // == target ，返回最大值的索引
    private static <E extends Comparable<E>> int ceil(E[] data, E target) {
        int upper = upper(data, target);
        if ((upper - 1 >= 0) && data[upper - 1].compareTo(target) == 0) {
            return upper - 1;
        }
        return upper;
    }

}
